#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    //剑指 Offer 27. 二叉树的镜像
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr)
        {
            return nullptr;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            TreeNode* cur = q.front();
            q.pop();

            TreeNode* old_right = cur->right;
            TreeNode* old_left = cur->left;

            cur->right = old_left;
            cur->left = old_right;

            if (cur->left)
                q.push(cur->left);
            if (cur->right)
                q.push(cur->right);
        }
        return root;
    }

    //剑指 Offer 28. 对称的二叉树
    bool isSame(TreeNode* root1, TreeNode* root2)
    {
        if (root1 == nullptr && root2 == nullptr)
        {
            return true;
        }
        if (root1 == nullptr || root2 == nullptr)
        {
            return false;
        }

        return (root1->val == root2->val) 
        && isSame(root1->left, root2->right)
        && isSame(root1->right, root2->left);
    }

    bool isSymmetric(TreeNode* root) {
        if (root == nullptr)
        {
            return true;
        }
        return isSame(root->left, root->right);
    }
};